In the field of computer science, programmers have developed various data structures to deal with common problems. Data structures can be fashioned to help conserve processing resources and process data more efficiently. Choosing the proper data structure is thus an important part of software design.
For example, in the case of representing user interface elements that are to be displayed as part of a user interface, a tree type sometimes called a “simple tree” can be used. Nodes in the tree can represent the user interface elements. The nodes can contain various pointers to facilitate easy navigation of the elements via the tree.
FIG. 1 shows an example of a user interface 100 with elements 112, 122, 124, 126, 128, 132, 134, and 136. FIG. 2 shows a corresponding exemplary simple tree 200 for representing the user interface 100 of FIG. 1. The simple tree 200 includes the elements 212, 222, 224, 226, 228, 232, 234, and 236, each of which correspond to a user interface element shown in FIG. 1.
The simple tree 200 preserves the hierarchical relationship between the elements. Nodes in the simple tree 200 include a pointer to a parent node, if any, the previous node (e.g., sibling), if any, the next node (e.g., sibling), if any, and the first child node, if any. Accordingly, navigation in the user interface is easily accomplished because parent, adjacent (e.g., next sibling), and child nodes are easily found.
Separately, in a scenario involving representation of formatted text, a tree type sometimes call a “sequential tree” can be used. FIG. 3 shows an example of formatted text 300. In the example, the word “TREE” has been formatted to be bold.
FIG. 4 depicts an exemplary sequential tree 400 for representing the formatted text 300 of FIG. 3. The sequential tree 400 includes the tree nodes 412 and 422, the linking data structure 430 (i.e., nodes 432, 434, 435, 436, and 438), and the text store 452. The linking data structure 430 can be implemented as a binary splay tree to facilitate processing text in the text store 452.
The nodes of the sequential tree can include formatting nodes, such as the bold node 422. Text enclosed by the bold node is designated to be formatted as bold. Given a particular character position, navigation can be easily accomplished to the enclosing formatting nodes in a bottom-up fashion. Also, searching for text is easily accomplished because the text is stored sequentially in the text store 452. The text store 452 can be implemented as a series of linked smaller stores with empty spaces (e.g., null padding) therein so that large blocks of text can be edited while avoiding large copy and move operations.
Although the trees discussed above are suitable for their depicted purposes, there remains room for improvement in utilizing them and other data structures.